/*
 * bst/thread_node.hh - Threaded node implementation.
 * Copyright (C) 2008  Mikhail Vorozhtsov
 * See the LICENSE section of the README file for details.
 */

/* $Id$ */

#ifndef HEADER_LIBBST_MJ_THREAD_NODE_HH
#define HEADER_LIBBST_MJ_THREAD_NODE_HH

#include HEADER (LIBBST_PREFIX,base.hh)

START_NAMESPACE (LIBBST_NS)

template <class P>
class wrap_thread_node_t : public P
{
public:
  INLINE
  wrap_thread_node_t *
  get_left () const
  {
    return this->left_thread_p () ? NULL
           : (wrap_thread_node_t *) this->get_left_ptr ();
  }

  INLINE
  wrap_thread_node_t *
  get_right () const
  {
    return this->right_thread_p () ? NULL
           : (wrap_thread_node_t *) this->get_right_ptr ();
  }
};

struct basic_thread_node_t : basic_node_t
{
public:
  INLINE
  bool
  left_thread_p () const
  {
    return left.bit0;
  }

  INLINE
  void
  set_left_thread (bool x)
  {
    left.bit0 = x;
  }

  INLINE
  basic_thread_node_t *
  get_left_ptr () const
  {
    return (basic_thread_node_t *) (left.raw & BASE_MASK);
  }

  INLINE
  void
  set_left_ptr (basic_thread_node_t *x)
  {
    left.base = (u64_t) x >> BASE_SHIFT;
  }

  INLINE
  bool
  right_thread_p () const
  {
    return right.bit0;
  }

  INLINE
  void
  set_right_thread (bool x)
  {
    right.bit0 = x;
  }

  INLINE
  basic_thread_node_t *
  get_right_ptr () const
  {
    return (basic_thread_node_t *) (right.raw & BASE_MASK);
  }

  INLINE
  void
  set_right_ptr (basic_thread_node_t *x)
  {
    right.base = (u64_t) x >> BASE_SHIFT;
  }
};

template <typename T, class P = T, u64_t OFFSET = 0,
          typename CMP = compare<T, T> >
class thread_node_t
  : public base_node_t<T, wrap_thread_node_t<P>, OFFSET, CMP>
{
private:
  typedef thread_node_t node_t;
  typedef base_node_t<T, wrap_thread_node_t<P>, OFFSET, CMP> parent_t;

protected:
  INLINE
  node_t *
  get_left_ptr ()
  {
    return (node_t *) P::get_left_ptr ();
  }

  INLINE
  node_t *
  get_right_ptr ()
  {
    return (node_t *) P::get_right_ptr ();
  }

public:
  __LIBBST_MJ_NODE_WRAPPERS

  template <typename TREE>
  node_t *
  get_prev (TREE *tree UNUSED)
  {
    node_t *left = this->get_left_ptr ();

    if (this->left_thread_p ())
      return left;
    else
      {
        node_t *parent;
        return left->get_max (parent);
      }
  };

  template <typename TREE>
  node_t *
  get_next (TREE *tree UNUSED)
  {
    node_t *right = this->get_right_ptr ();

    if (this->right_thread_p ())
      return right;
    else
      {
        node_t *parent;
        return right->get_min (parent);
      }
  };

public:
  template <typename TREE>
  node_t *
  get_parent (TREE *tree, node_t *top UNUSED)
  {
    node_t *left, *right;

    if (this == tree->get_root ())
      return NULL;

    if (this->left_thread_p () && this->right_thread_p ())
      {
        left = this->get_left_ptr ();

        if (left && left->get_right_ptr () == this)
          return left;
        else
          return this->get_right_ptr ();
      }

    left = this;

    while (!left->left_thread_p ())
      left = left->get_left_ptr ();

    left = left->get_left_ptr ();

    if (left)
      {
        right = left->get_right_ptr ();

        if (right == this)
          return left;

        for (left = right->get_left_ptr (); left != this;
             left = right->get_left_ptr ())
          right = left;

        return right;
      }

    right = this;

    while (!right->right_thread_p ())
      right = right->get_right_ptr ();

    return right->get_right_ptr ();
  }

  template <typename TREE>
  void
  insert (TREE *tree, node_t *parent, bool left_p, node_t *prev_or_next UNUSED)
  {
    this->set_left_thread (true);
    this->set_right_thread (true);

    if (parent)
      {
        if (left_p)
          {
            this->set_left_ptr (parent->get_left_ptr ());
            this->set_right_ptr (parent);
            parent->set_left_thread (false);
            parent->set_left_ptr (this);
          }
        else
          {
            this->set_left_ptr (parent);
            this->set_right_ptr (parent->get_right_ptr ());
            parent->set_right_thread (false);
            parent->set_right_ptr (this);
          }
      }
    else
      {
        this->set_left_ptr (NULL);
        this->set_right_ptr (NULL);
        tree->set_root (this);
      }
  }

  template <typename TREE>
  void
  remove (TREE *tree, node_t *parent, bool left_p, node_t *prev_or_next UNUSED)
  {
    if (parent)
      {
        if (left_p)
          {
            parent->set_left_thread (true);
            parent->set_left_ptr (this->get_left_ptr ());
          }
        else
          {
            parent->set_right_thread (true);
            parent->set_right_ptr (this->get_right_ptr ());
          }
      }
    else
      tree->set_root (NULL);
  }

  template <typename TREE>
  node_t *
  replace_with_pred (TREE *tree, node_t *parent, bool left_p, node_t *pred,
                     node_t *pred_parent, node_t *&succ)
  {
    node_t *left = this->get_left_ptr ();
    node_t *right = this->get_right_ptr ();
    bool right_thread_p = this->right_thread_p ();
    node_t *pred_left = pred->get_left_ptr ();
    bool pred_left_thread_p = pred->left_thread_p ();

    pred->set_right_thread (right_thread_p);
    pred->set_right_ptr (right);

    if (!right_thread_p)
      {
        while (!right->left_thread_p ())
          right = right->get_left_ptr ();

        right->set_left_ptr (pred);
        succ = right;
      }

    if (pred_parent != this)
      {
        if (pred_left_thread_p)
          {
            pred->set_left_thread (false);
            pred_parent->set_right_thread (true);
            pred_parent->set_right_ptr (pred);
          }
        else
          pred_parent->set_right_ptr (pred_left);

        pred->set_left_ptr (left);
      }

    if (parent)
      {
        if (left_p)
          parent->set_left_ptr (pred);
        else
          parent->set_right_ptr (pred);
      }
    else
      tree->set_root (pred);

    return pred_left_thread_p ? NULL : pred_left;
  }

  template <typename TREE>
  node_t *
  replace_with_succ (TREE *tree, node_t *parent, bool left_p, node_t *succ,
                     node_t *succ_parent, node_t *prev_or_next UNUSED)
  {
    node_t *left = this->get_left_ptr ();
    node_t *right = this->get_right_ptr ();
    node_t *succ_right = succ->get_right_ptr ();
    bool succ_right_thread_p = succ->right_thread_p ();

    succ->set_left_thread (true);
    succ->set_left_ptr (left);

    if (succ_parent != this)
      {
        if (succ_right_thread_p)
          {
            succ->set_right_thread (false);
            succ_parent->set_left_thread (true);
            succ_parent->set_left_ptr (succ);
          }
        else
          succ_parent->set_left_ptr (succ_right);

        succ->set_right_ptr (right);
      }

    if (parent)
      {
        if (left_p)
          parent->set_left_ptr (succ);
        else
          parent->set_right_ptr (succ);
      }
    else
      tree->set_root (succ);

    return succ_right_thread_p ? NULL : succ_right;
  }

  template <typename TREE>
  node_t *
  rotate_left (TREE *tree, node_t *parent)
  {
    node_t *pivot = this->get_right_ptr ();
    node_t *pivot_left = pivot->get_left_ptr ();

    pivot->set_left_ptr (this);

    if (!pivot->left_thread_p ())
      {
        this->set_right_ptr (pivot_left);

        while (!pivot_left->left_thread_p ())
          pivot_left = pivot_left->get_left_ptr ();

        pivot_left->set_left_ptr (this);
      }
    else
      {
        pivot->set_left_thread (false);
        this->set_right_ptr (pivot);
        this->set_right_thread (true);
      }

    if (parent)
      {
        if (this == parent->get_left_ptr ())
          parent->set_left_ptr (pivot);
        else
          parent->set_right_ptr (pivot);
      }
    else
      tree->set_root (pivot);

    return pivot;
  }

  template <typename TREE>
  node_t *
  rotate_right (TREE *tree, node_t *parent)
  {
    node_t *pivot = this->get_left_ptr ();
    node_t *pivot_right = pivot->get_right_ptr ();

    pivot->set_right_ptr (this);

    if (!pivot->right_thread_p ())
      {
        this->set_left_ptr (pivot_right);

        while (!pivot_right->right_thread_p ())
          pivot_right = pivot_right->get_right_ptr ();

        pivot_right->set_right_ptr (this);
      }
    else
      {
        pivot->set_right_thread (false);
        this->set_left_ptr (pivot);
        this->set_left_thread (true);
      }

    if (parent)
      {
        if (this == parent->get_left_ptr ())
          parent->set_left_ptr (pivot);
        else
          parent->set_right_ptr (pivot);
      }
    else
      tree->set_root (pivot);

    return pivot;
  }

  template <typename TREE>
  void
  replace (TREE *tree, node_t *with)
  {
    node_t *parent = this->get_parent (tree, tree->get_root ());

    if (parent)
      {
        if (parent->get_left_ptr () == this)
          parent->set_left_ptr (with);
        else
          parent->set_right_ptr (with);
      }
    else
      tree->set_root (with);

    if (!this->left_thread_p ())
      this->get_prev (tree)->set_right_ptr (with);

    if (!this->right_thread_p ())
      this->get_next (tree)->set_left_ptr (with);

    with->set_left_thread (this->left_thread_p ());
    with->set_left_ptr (this->get_left_ptr ());
    with->set_right_thread (this->right_thread_p ());
    with->set_right_ptr (this->get_right_ptr ());
  }
};

END_NAMESPACE

#endif /* HEADER_LIBBST_MJ_THREAD_NODE_HH */

